{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Logical OR of Two Binary Grids Represented as Quad-Trees"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #divide-and-conquer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #分治"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: intersect"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #四叉树交集"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>二进制矩阵中的所有元素不是 <strong>0</strong> 就是 <strong>1 </strong>。</p>\n",
    "\n",
    "<p>给你两个四叉树，<code>quadTree1</code> 和 <code>quadTree2</code>。其中 <code>quadTree1</code> 表示一个 <code>n * n</code> 二进制矩阵，而 <code>quadTree2</code> 表示另一个 <code>n * n</code> 二进制矩阵。</p>\n",
    "\n",
    "<p>请你返回一个表示 <code>n * n</code> 二进制矩阵的四叉树，它是 <code>quadTree1</code> 和 <code>quadTree2</code> 所表示的两个二进制矩阵进行 <strong>按位逻辑或运算</strong> 的结果。</p>\n",
    "\n",
    "<p>注意，当 <code>isLeaf</code> 为 <strong>False </strong>时，你可以把 <strong>True</strong> 或者 <strong>False</strong> 赋值给节点，两种值都会被判题机制 <strong>接受</strong> 。</p>\n",
    "\n",
    "<p>四叉树数据结构中，每个内部节点只有四个子节点。此外，每个节点都有两个属性：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>val</code>：储存叶子结点所代表的区域的值。1 对应 <strong>True</strong>，0 对应 <strong>False</strong>；</li>\n",
    "\t<li><code>isLeaf</code>: 当这个节点是一个叶子结点时为 <strong>True</strong>，如果它有 4 个子节点则为 <strong>False</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<pre>\n",
    "class Node {\n",
    "    public boolean val;\n",
    "    public boolean isLeaf;\n",
    "    public Node topLeft;\n",
    "    public Node topRight;\n",
    "    public Node bottomLeft;\n",
    "    public Node bottomRight;\n",
    "}</pre>\n",
    "\n",
    "<p>我们可以按以下步骤为二维区域构建四叉树：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>如果当前网格的值相同（即，全为 <code>0</code> 或者全为 <code>1</code>），将 <code>isLeaf</code> 设为 True ，将 <code>val</code> 设为网格相应的值，并将四个子节点都设为 Null 然后停止。</li>\n",
    "\t<li>如果当前网格的值不同，将 <code>isLeaf</code> 设为 False， 将 <code>val</code> 设为任意值，然后如下图所示，将当前网格划分为四个子网格。</li>\n",
    "\t<li>使用适当的子网格递归每个子节点。</li>\n",
    "</ol>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/11/new_top.png\" style=\"height: 181px; width: 777px;\" /></p>\n",
    "\n",
    "<p>如果你想了解更多关于四叉树的内容，可以参考 <a href=\"https://en.wikipedia.org/wiki/Quadtree\">wiki</a> 。</p>\n",
    "\n",
    "<p><strong>四叉树格式：</strong></p>\n",
    "\n",
    "<p>输出为使用层序遍历后四叉树的序列化形式，其中 <code>null</code> 表示路径终止符，其下面不存在节点。</p>\n",
    "\n",
    "<p>它与二叉树的序列化非常相似。唯一的区别是节点以列表形式表示 <code>[isLeaf, val]</code> 。</p>\n",
    "\n",
    "<p>如果 <code>isLeaf</code> 或者 <code>val</code> 的值为 True ，则表示它在列表 <code>[isLeaf, val]</code> 中的值为 <strong>1</strong> ；如果 <code>isLeaf</code> 或者 <code>val</code> 的值为 False ，则表示值为 <strong>0 </strong>。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/11/qt1.png\" style=\"height: 196px; width: 550px;\" /> <img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/11/qt2.png\" style=\"height: 278px; width: 550px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>quadTree1 = [[0,1],[1,1],[1,1],[1,0],[1,0]]\n",
    ", quadTree2 = [[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]\n",
    "<strong>输出：</strong>[[0,0],[1,1],[1,1],[1,1],[1,0]]\n",
    "<strong>解释：</strong>quadTree1 和 quadTree2 如上所示。由四叉树所表示的二进制矩阵也已经给出。\n",
    "如果我们对这两个矩阵进行按位逻辑或运算，则可以得到下面的二进制矩阵，由一个作为结果的四叉树表示。\n",
    "注意，我们展示的二进制矩阵仅仅是为了更好地说明题意，你无需构造二进制矩阵来获得结果四叉树。\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/02/11/qtr.png\" style=\"height: 222px; width: 777px;\" />\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>quadTree1 = [[1,0]]\n",
    ", quadTree2 = [[1,0]]\n",
    "<strong>输出：</strong>[[1,0]]\n",
    "<strong>解释：</strong>两个数所表示的矩阵大小都为 1*1，值全为 0 \n",
    "结果矩阵大小为 1*1，值全为 0 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>quadTree1 = [[0,0],[1,0],[1,0],[1,1],[1,1]]\n",
    ", quadTree2 = [[0,0],[1,1],[1,1],[1,0],[1,1]]\n",
    "<strong>输出：</strong>[[1,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>quadTree1 = [[0,0],[1,1],[1,0],[1,1],[1,1]]\n",
    ", quadTree2 = [[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]\n",
    "<strong>输出：</strong>[[0,0],[1,1],[0,1],[1,1],[1,1],null,null,null,null,[1,1],[1,0],[1,0],[1,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 5：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>quadTree1 = [[0,1],[1,0],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]\n",
    ", quadTree2 = [[0,1],[0,1],[1,0],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1]]\n",
    "<strong>输出：</strong>[[0,0],[0,1],[0,1],[1,1],[1,0],[1,0],[1,0],[1,1],[1,1],[1,0],[1,0],[1,1],[1,1]]\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>quadTree1</code> 和 <code>quadTree2</code> 都是符合题目要求的四叉树，每个都代表一个 <code>n * n</code> 的矩阵。</li>\n",
    "\t<li><code>n == 2^x</code> ，其中 <code>0 <= x <= 9</code>.</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [logical-or-of-two-binary-grids-represented-as-quad-trees](https://leetcode.cn/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [logical-or-of-two-binary-grids-represented-as-quad-trees](https://leetcode.cn/problems/logical-or-of-two-binary-grids-represented-as-quad-trees/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[0,1],[1,1],[1,1],[1,0],[1,0]]\\n[[0,1],[1,1],[0,1],[1,1],[1,0],null,null,null,null,[1,0],[1,0],[1,1],[1,1]]', '[[1,0]]\\n[[1,0]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        def dfs(node1, node2):\n",
    "            if node1.isLeaf:\n",
    "                if node1.val:\n",
    "                    return node1\n",
    "                else:\n",
    "                    return node2\n",
    "            if node2.isLeaf:\n",
    "                if node2.val:\n",
    "                    return node2\n",
    "                else:\n",
    "                    return node1\n",
    "            topLeft = dfs(node1.topLeft, node2.topLeft)\n",
    "            topRight = dfs(node1.topRight, node2.topRight)\n",
    "            bottomLeft = dfs(node1.bottomLeft, node2.bottomLeft)\n",
    "            bottomRight = dfs(node1.bottomRight, node2.bottomRight)\n",
    "            if topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and \\\n",
    "                    topLeft.val == topRight.val == bottomLeft.val == bottomRight.val:\n",
    "                return Node(topLeft.val, True, None, None, None, None)\n",
    "            else:\n",
    "                return Node(0, False, topLeft, topRight, bottomLeft, bottomRight)\n",
    "\n",
    "        return dfs(quadTree1, quadTree2)\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return Node(True, True, None, None, None, None) if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf:\n",
    "            return Node(True, True, None, None, None, None) if quadTree2.val else quadTree1\n",
    "        tl, tr, bl, br = self.intersect(quadTree1.topLeft, quadTree2.topLeft), self.intersect(quadTree1.topRight, quadTree2.topRight), self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft), self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "        return Node(tl.val, True, None, None, None, None) if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val == tr.val == bl.val == br.val else Node(False, False, tl, tr, bl, br)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return Node(True,True) if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf:\n",
    "            return Node(True,True) if quadTree2.val else quadTree1\n",
    "        o1 = self.intersect(quadTree1.topLeft,quadTree2.topLeft)\n",
    "        o2 = self.intersect(quadTree1.topRight,quadTree2.topRight)\n",
    "        o3 = self.intersect(quadTree1.bottomLeft,quadTree2.bottomLeft)\n",
    "        o4 = self.intersect(quadTree1.bottomRight,quadTree2.bottomRight)\n",
    "        if o1.isLeaf and o2.isLeaf and o3.isLeaf and o4.isLeaf and o1.val == o2.val == o3.val == o4.val:\n",
    "            return Node(o1.val, True)\n",
    "        return Node(False, False, o1,o2,o3,o4)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        return self.dfs(quadTree1, quadTree2)\n",
    "\n",
    "    def dfs(self, quadTree1, quadTree2):\n",
    "        if quadTree1.isLeaf:\n",
    "            if quadTree1.val:\n",
    "                return quadTree1\n",
    "            else:\n",
    "                return quadTree2\n",
    "        elif quadTree2.isLeaf:\n",
    "            if quadTree2.val:\n",
    "                return quadTree2\n",
    "            else:\n",
    "                return quadTree1\n",
    "        else:\n",
    "            ret = Node(False, False)\n",
    "            ret.topLeft = self.dfs(quadTree1.topLeft, quadTree2.topLeft)\n",
    "            ret.topRight = self.dfs(quadTree1.topRight, quadTree2.topRight)\n",
    "            ret.bottomLeft = self.dfs(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "            ret.bottomRight = self.dfs(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "            if ret.topLeft.isLeaf and ret.topLeft.val and ret.topRight.isLeaf and ret.topRight.val and ret.bottomLeft.isLeaf and ret.bottomLeft.val and ret.bottomRight.isLeaf and ret.bottomRight.val:\n",
    "                ret.topLeft = ret.topRight = ret.bottomLeft = ret.bottomRight = None\n",
    "                ret.isLeaf = ret.val = True\n",
    "\n",
    "        return ret\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return Node(True, True) if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf:\n",
    "            return self.intersect(quadTree2, quadTree1)\n",
    "        o1 = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "        o2 = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "        o3 = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "        o4 = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "        if o1.isLeaf and o2.isLeaf and o3.isLeaf and o4.isLeaf and o1.val == o2.val == o3.val == o4.val:\n",
    "            return Node(o1.val, True)\n",
    "        return Node(False, False, o1, o2, o3, o4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        # 如果是leaf就返回有值的那个\n",
    "        if (quadTree1.isLeaf and quadTree1.val) or (quadTree2.isLeaf and not quadTree2.val):\n",
    "            return quadTree1\n",
    "        elif (quadTree1.isLeaf and not quadTree1.val) or (quadTree2.isLeaf and quadTree2.val):\n",
    "            return quadTree2\n",
    "        \n",
    "        # 不是leaf的情况就要考虑4个方向\n",
    "        else:\n",
    "            res = Node(\"*\", False, None, None, None)\n",
    "            res.topLeft = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "            res.topRight = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "            res.bottomLeft = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "            res.bottomRight = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "            # 如果4个点都是叶子并且相等的时候要合并\n",
    "            if res.topLeft.isLeaf and res.topRight.isLeaf and res.bottomLeft.isLeaf and res.bottomRight.isLeaf and res.topLeft.val == res.topRight.val == res.bottomLeft.val == res.bottomRight.val:\n",
    "                res = res.topLeft\n",
    "            return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        def dfs(node1, node2):\n",
    "            if not node1:   return node2\n",
    "            if not node2:   return node1\n",
    "            \n",
    "            if node1.isLeaf and node1.val:  return node1\n",
    "            if node2.isLeaf and node2.val:  return node2\n",
    "\n",
    "            node1.topLeft = dfs(node1.topLeft, node2.topLeft)\n",
    "            node1.topRight = dfs(node1.topRight, node2.topRight)\n",
    "            node1.bottomLeft = dfs(node1.bottomLeft, node2.bottomLeft)\n",
    "            node1.bottomRight = dfs(node1.bottomRight, node2.bottomRight)\n",
    "            if node1.topLeft and node1.topRight and node1.bottomLeft and node1.bottomRight and node1.topLeft.val + node1.topRight.val + node1.bottomLeft.val + node1.bottomRight.val + node1.topLeft.isLeaf + node1.topRight.isLeaf + node1.bottomLeft.isLeaf + node1.bottomRight.isLeaf == 8:\n",
    "                node1.topLeft = node1.topRight = node1.bottomLeft = node1.bottomRight = None\n",
    "                node1.val = 1\n",
    "                node1.isLeaf = 1\n",
    "            else:\n",
    "                node1.isLeaf &= node2.isLeaf\n",
    "            return node1\n",
    "        return dfs(quadTree1, quadTree2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return Node(True, True, None, None, None, None) if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf:\n",
    "            return Node(True, True, None, None, None, None) if quadTree2.val else quadTree1\n",
    "        tl, tr, bl, br = self.intersect(quadTree1.topLeft, quadTree2.topLeft), self.intersect(quadTree1.topRight, quadTree2.topRight), self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft), self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "        return Node(tl.val, True, None, None, None, None) if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val == tr.val == bl.val == br.val else Node(False, False, tl, tr, bl, br)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return Node(True, True) if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf:\n",
    "            return self.intersect(quadTree2, quadTree1)\n",
    "        o1 = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "        o2 = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "        o3 = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "        o4 = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "        if o1.isLeaf and o2.isLeaf and o3.isLeaf and o4.isLeaf and o1.val == o2.val == o3.val == o4.val:\n",
    "            return Node(o1.val, True)\n",
    "        return Node(False, False, o1, o2, o3, o4)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def B(self,a,b):\n",
    "        if a == 0 and b == 0:\n",
    "            return 0\n",
    "        return 1\n",
    "    def A(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf and quadTree2.isLeaf:\n",
    "            return Node(self.B(quadTree1.val,quadTree2.val),True)\n",
    "        elif quadTree1.isLeaf and quadTree1.val == 1:\n",
    "            return Node(1,True)\n",
    "        elif quadTree1.isLeaf and quadTree1.val == 0:\n",
    "            quadTree1 = quadTree2\n",
    "        elif quadTree2.isLeaf and quadTree2.val == 1:\n",
    "            return Node(1,True)\n",
    "        elif quadTree2.isLeaf and quadTree2.val == 0:\n",
    "            quadTree2 = quadTree1\n",
    "        n1 = self.A(quadTree1.topLeft,quadTree2.topLeft)   \n",
    "        n2 = self.A(quadTree1.topRight,quadTree2.topRight)  \n",
    "        n3 = self.A(quadTree1.bottomLeft,quadTree2.bottomLeft)  \n",
    "        n4 = self.A(quadTree1.bottomRight,quadTree2.bottomRight)   \n",
    "        if n1.isLeaf == True and n1.val == 1 and n2.isLeaf == True and n2.val == 1 and n3.isLeaf == True and n3.val == 1 and n4.isLeaf == True and n4.val == 1:\n",
    "            return Node(1,True)\n",
    "        if n1.isLeaf == True and n1.val == 0 and n2.isLeaf == True and n2.val == 0 and n3.isLeaf == True and n3.val == 0 and n4.isLeaf == True and n4.val == 0:\n",
    "            return Node(0,True)\n",
    "        return Node(0,False,n1,n2,n3,n4)\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        return self.A(quadTree1,quadTree2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return quadTree1 if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf:\n",
    "            return quadTree2 if quadTree2.val else quadTree1\n",
    "        quadTree1.topLeft = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "        quadTree1.topRight = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "        quadTree1.bottomLeft = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "        quadTree1.bottomRight = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "\n",
    "        if all([quadTree1.topLeft.isLeaf, quadTree1.topRight.isLeaf, quadTree1.bottomLeft.isLeaf, quadTree1.bottomRight.isLeaf]):\n",
    "            val1 = all([quadTree1.topLeft.val, quadTree1.topRight.val, quadTree1.bottomLeft.val, quadTree1.bottomRight.val])\n",
    "            val0 = not any([quadTree1.topLeft.val, quadTree1.topRight.val, quadTree1.bottomLeft.val, quadTree1.bottomRight.val])\n",
    "\n",
    "            if val0 or val1:\n",
    "                quadTree1.isLeaf = True\n",
    "                quadTree1.val = val1\n",
    "                quadTree1.topLeft = None\n",
    "                quadTree1.topRight = None\n",
    "                quadTree1.bottomRight = None\n",
    "                quadTree1.bottomLeft = None\n",
    "\n",
    "\n",
    "        return quadTree1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return Node(True, True) if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf:\n",
    "            return self.intersect(quadTree2,quadTree1)\n",
    "        o1 = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "        o2 = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "        o3 = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "        o4 = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "        if o1.isLeaf and o2.isLeaf and o3.isLeaf and o4.isLeaf and o1.val==o2.val==o3.val==o4.val:\n",
    "            return Node(o1.val, True)\n",
    "        return Node(False, False, o1, o2, o3, o4)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "      if quadTree1.isLeaf:\n",
    "        return Node(True,True,None,None,None,None) if quadTree1.val==True else quadTree2\n",
    "      if quadTree2.isLeaf:\n",
    "        return Node(True,True,None,None,None,None) if quadTree2.val==True else quadTree1\n",
    "      tl,tr,bl,br=self.intersect(quadTree1.topLeft,quadTree2.topLeft),self.intersect(quadTree1.topRight,quadTree2.topRight),self.intersect(quadTree1.bottomLeft,quadTree2.bottomLeft),self.intersect(quadTree1.bottomRight,quadTree2.bottomRight)\n",
    "      return Node(tl.val,True,None,None,None,None) if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val==tr.val==bl.val==br.val else Node(False,False,tl,tr,bl,br)\n",
    "      \n",
    "      \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        def dfs(quadTree1,quadTree2):\n",
    "            if quadTree1==None:\n",
    "                return quadTree2\n",
    "            if quadTree2==None:\n",
    "                return quadTree1\n",
    "            if (quadTree1.val==1 and quadTree1.isLeaf==1) or (quadTree2.val==1 and quadTree2.isLeaf==1):\n",
    "                quadTree1.isLeaf=True\n",
    "                quadTree1.topLeft=None\n",
    "                quadTree1.topRight=None\n",
    "                quadTree1.bottomLeft=None\n",
    "                quadTree1.bottomRight=None\n",
    "                quadTree1.val=1\n",
    "                return quadTree1\n",
    "            if quadTree1.isLeaf==True and quadTree2.isLeaf==True:\n",
    "                quadTree1.val=0\n",
    "                return quadTree1\n",
    "            quadTree1.isLeaf=False\n",
    "            quadTree1.topLeft=dfs(quadTree1.topLeft,quadTree2.topLeft)\n",
    "            quadTree1.topRight=dfs(quadTree1.topRight,quadTree2.topRight)\n",
    "            quadTree1.bottomLeft=dfs(quadTree1.bottomLeft,quadTree2.bottomLeft)\n",
    "            quadTree1.bottomRight=dfs(quadTree1.bottomRight,quadTree2.bottomRight)\n",
    "            if quadTree1.topLeft.val==quadTree1.topRight.val==quadTree1.bottomLeft.val==quadTree1.bottomRight.val and quadTree1.topLeft.isLeaf==quadTree1.topRight.isLeaf==quadTree1.bottomLeft.isLeaf==quadTree1.bottomRight.isLeaf==True:\n",
    "                quadTree1.isLeaf=True\n",
    "                quadTree1.val=quadTree1.topLeft.val\n",
    "                quadTree1.topLeft=None\n",
    "                quadTree1.topRight=None\n",
    "                quadTree1.bottomLeft=None\n",
    "                quadTree1.bottomRight=None\n",
    "            return quadTree1\n",
    "        dfs(quadTree1,quadTree2)\n",
    "        return quadTree1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        # 如果是leaf就返回有值的那个\n",
    "        if (quadTree1.isLeaf and quadTree1.val) or (quadTree2.isLeaf and not quadTree2.val):\n",
    "            return quadTree1\n",
    "        elif (quadTree1.isLeaf and not quadTree1.val) or (quadTree2.isLeaf and quadTree2.val):\n",
    "            return quadTree2\n",
    "        \n",
    "        # 不是leaf的情况就要考虑4个方向\n",
    "        else:\n",
    "            res = Node(\"*\", False, None, None, None)\n",
    "            res.topLeft = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "            res.topRight = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "            res.bottomLeft = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "            res.bottomRight = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "            # 如果4个点都是叶子并且相等的时候要合并\n",
    "            if res.topLeft.isLeaf and res.topRight.isLeaf and res.bottomLeft.isLeaf and res.bottomRight.isLeaf and res.topLeft.val == res.topRight.val == res.bottomLeft.val == res.bottomRight.val:\n",
    "                res = res.topLeft\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        def dfs(quadTree1,quadTree2):\n",
    "            if quadTree1==None:\n",
    "                return quadTree2\n",
    "            if quadTree2==None:\n",
    "                return quadTree1\n",
    "            if (quadTree1.val==1 and quadTree1.isLeaf==1) or (quadTree2.val==1 and quadTree2.isLeaf==1):\n",
    "                quadTree1.isLeaf=True\n",
    "                quadTree1.topLeft=None\n",
    "                quadTree1.topRight=None\n",
    "                quadTree1.bottomLeft=None\n",
    "                quadTree1.bottomRight=None\n",
    "                quadTree1.val=1\n",
    "                return quadTree1\n",
    "            if quadTree1.isLeaf==True and quadTree2.isLeaf==True:\n",
    "                quadTree1.val=0\n",
    "                return quadTree1\n",
    "            quadTree1.isLeaf=False\n",
    "            quadTree1.topLeft=dfs(quadTree1.topLeft,quadTree2.topLeft)\n",
    "            quadTree1.topRight=dfs(quadTree1.topRight,quadTree2.topRight)\n",
    "            quadTree1.bottomLeft=dfs(quadTree1.bottomLeft,quadTree2.bottomLeft)\n",
    "            quadTree1.bottomRight=dfs(quadTree1.bottomRight,quadTree2.bottomRight)\n",
    "            if quadTree1.topLeft.val==quadTree1.topRight.val==quadTree1.bottomLeft.val==quadTree1.bottomRight.val and quadTree1.topLeft.isLeaf==quadTree1.topRight.isLeaf==quadTree1.bottomLeft.isLeaf==quadTree1.bottomRight.isLeaf==True:\n",
    "                quadTree1.isLeaf=True\n",
    "                quadTree1.val=quadTree1.topLeft.val\n",
    "                quadTree1.topLeft=None\n",
    "                quadTree1.topRight=None\n",
    "                quadTree1.bottomLeft=None\n",
    "                quadTree1.bottomRight=None\n",
    "            return quadTree1\n",
    "        dfs(quadTree1,quadTree2)\n",
    "        def f(quadTree1):\n",
    "            # print(quadTree1.isLeaf)\n",
    "            # print(quadTree1.topLeft)\n",
    "            # print(quadTree1.topRight)\n",
    "            # print(quadTree1.bottomLeft)\n",
    "            # print(quadTree1.bottomRight)\n",
    "            if quadTree1.isLeaf==False:\n",
    "                f(quadTree1.topLeft)\n",
    "                f(quadTree1.topRight)\n",
    "                f(quadTree1.bottomLeft)\n",
    "                f(quadTree1.bottomRight)\n",
    "            if quadTree1.isLeaf==True:\n",
    "                if quadTree1.topLeft!=None:\n",
    "                    print('sa')\n",
    "                if quadTree1.topRight!=None:\n",
    "                    print('sa')\n",
    "                if quadTree1.bottomLeft!=None:\n",
    "                    print('sa')\n",
    "                if quadTree1.bottomRight!=None:\n",
    "                    print('sa')\n",
    "        f(quadTree1)\n",
    "        return quadTree1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return quadTree2 if not quadTree1.val else Node(True, True, None, None, None, None)\n",
    "        if quadTree2.isLeaf:\n",
    "            return quadTree1 if not quadTree2.val else Node(True, True, None, None, None, None)\n",
    "\n",
    "        tl = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "        tr = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "        bl = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "        br = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "        if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val is tr.val is bl.val is br.val:\n",
    "            return Node(tl.val, True, None, None, None, None)\n",
    "        return Node(False, False, tl, tr, bl, br)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        t1, t2 = quadTree1, quadTree2\n",
    "        if t1.isLeaf:\n",
    "            return Node(True, True) if t1.val else t2\n",
    "        if t2.isLeaf:\n",
    "            return Node(True, True) if t2.val else t1\n",
    "        tl = self.intersect(t1.topLeft, t2.topLeft)\n",
    "        tr = self.intersect(t1.topRight, t2.topRight)\n",
    "        bl = self.intersect(t1.bottomLeft, t2.bottomLeft)\n",
    "        br = self.intersect(t1.bottomRight, t2.bottomRight)\n",
    "        if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val == tr.val == bl.val == br.val:\n",
    "            return Node(tl.val, True)\n",
    "        return Node(False, False, tl, tr, bl, br)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        def dfs(tree1: Node, tree2: Node) -> Node:\n",
    "            if tree1.isLeaf:\n",
    "                return Node(True, True) if tree1.val else tree2\n",
    "            if tree2.isLeaf:\n",
    "                return dfs(tree2, tree1)\n",
    "            v1 = dfs(tree1.topLeft, tree2.topLeft)\n",
    "            v2 = dfs(tree1.topRight, tree2.topRight)\n",
    "            v3 = dfs(tree1.bottomLeft, tree2.bottomLeft)\n",
    "            v4 = dfs(tree1.bottomRight, tree2.bottomRight)\n",
    "            if v1.isLeaf and v2.isLeaf and v3.isLeaf and v4.isLeaf and v1.val == v2.val == v3.val == v4.val:\n",
    "                return Node(v1.val, True)\n",
    "            return Node(False, False, v1, v2, v3, v4)\n",
    "        return dfs(quadTree1, quadTree2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        def dfs(node1, node2):\n",
    "            if not node1:   return node2\n",
    "            if not node2:   return node1\n",
    "            \n",
    "            if node1.isLeaf and node1.val:  return node1\n",
    "            if node2.isLeaf and node2.val:  return node2\n",
    "\n",
    "            node1.topLeft = dfs(node1.topLeft, node2.topLeft)\n",
    "            node1.topRight = dfs(node1.topRight, node2.topRight)\n",
    "            node1.bottomLeft = dfs(node1.bottomLeft, node2.bottomLeft)\n",
    "            node1.bottomRight = dfs(node1.bottomRight, node2.bottomRight)\n",
    "            if node1.topLeft and node1.topRight and node1.bottomLeft and node1.bottomRight and node1.topLeft.val + node1.topRight.val + node1.bottomLeft.val + node1.bottomRight.val + node1.topLeft.isLeaf + node1.topRight.isLeaf + node1.bottomLeft.isLeaf + node1.bottomRight.isLeaf == 8:\n",
    "                node1.topLeft = node1.topRight = node1.bottomLeft = node1.bottomRight = None\n",
    "                node1.val = 1\n",
    "                node1.isLeaf = 1\n",
    "            else:\n",
    "                node1.isLeaf &= node2.isLeaf\n",
    "            return node1\n",
    "        return dfs(quadTree1, quadTree2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\r\n",
    "# Definition for a QuadTree node.\r\n",
    "class Node:\r\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\r\n",
    "        self.val = val\r\n",
    "        self.isLeaf = isLeaf\r\n",
    "        self.topLeft = topLeft\r\n",
    "        self.topRight = topRight\r\n",
    "        self.bottomLeft = bottomLeft\r\n",
    "        self.bottomRight = bottomRight\r\n",
    "\"\"\"\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\r\n",
    "        if quadTree1.isLeaf and quadTree2.isLeaf:\r\n",
    "            return Node(quadTree1.val | quadTree2.val,True)\r\n",
    "        \r\n",
    "        # leaf_node,parent_node=None,None\r\n",
    "        # if quadTree1.isLeaf:\r\n",
    "        #     leaf_node=quadTree1\r\n",
    "        #     parent_node=quadTree2\r\n",
    "        # else:\r\n",
    "        #     leaf_node=quadTree2\r\n",
    "        #     parent_node=quadTree1\r\n",
    "        \r\n",
    "        # topLeft=self.intersect(leaf_node,parent_node.topLeft)\r\n",
    "        # topRight=self.intersect(leaf_node,parent_node.topRight)\r\n",
    "        # bottomLeft=self.intersect(leaf_node,parent_node.bottomLeft)\r\n",
    "        # bottomRight=self.intersect(leaf_node,parent_node.bottomRight)\r\n",
    "\r\n",
    "        topLeft=self.intersect(quadTree1 if quadTree1.isLeaf else quadTree1.topLeft,quadTree2 if quadTree2.isLeaf else quadTree2.topLeft)\r\n",
    "\r\n",
    "        topRight=self.intersect(quadTree1 if quadTree1.isLeaf else quadTree1.topRight,quadTree2 if quadTree2.isLeaf else quadTree2.topRight)\r\n",
    "\r\n",
    "        bottomLeft=self.intersect(quadTree1 if quadTree1.isLeaf else quadTree1.bottomLeft,quadTree2 if quadTree2.isLeaf else quadTree2.bottomLeft)\r\n",
    "\r\n",
    "        bottomRight=self.intersect(quadTree1 if quadTree1.isLeaf else quadTree1.bottomRight,quadTree2 if quadTree2.isLeaf else quadTree2.bottomRight)\r\n",
    "\r\n",
    "        if topLeft.isLeaf and topRight.isLeaf and bottomLeft.isLeaf and bottomRight.isLeaf and topLeft.val==topRight.val==bottomLeft.val==bottomRight.val:\r\n",
    "            return Node(topLeft.val,isLeaf=True)\r\n",
    "        else:\r\n",
    "            return Node(0,isLeaf=False,topLeft=topLeft,topRight=topRight,bottomLeft=bottomLeft,bottomRight=bottomRight)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf:\n",
    "            return Node(True, True) if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf:\n",
    "            return self.intersect(quadTree2, quadTree1)\n",
    "        o1 = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "        o2 = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "        o3 = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "        o4 = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "        if o1.isLeaf and o2.isLeaf and o3.isLeaf and o4.isLeaf and o1.val == o2.val == o3.val == o4.val:\n",
    "            return Node(o1.val, True)\n",
    "        return Node(False, False, o1, o2, o3, o4)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect_val(self, quadTree: 'Node', x: int) -> 'Node':\n",
    "        return \n",
    "\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf and quadTree2.isLeaf:\n",
    "            quadTree1.val |= quadTree2.val\n",
    "            return quadTree1\n",
    "        if quadTree1.isLeaf:\n",
    "            return quadTree2 if not quadTree1.val else Node(1, True, None, None, None, None)\n",
    "        if quadTree2.isLeaf:\n",
    "            return quadTree1 if not quadTree2.val else Node(1, True, None, None, None, None)\n",
    "\n",
    "        tl = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "        tr = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "        bl = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "        br = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "        if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val == tr.val == bl.val == br.val:\n",
    "            return Node(tl.val, True, None, None, None, None)\n",
    "        return Node(0, False, tl, tr, bl, br)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        def dfs(node1, node2):\n",
    "            if not node1:   return node2\n",
    "            if not node2:   return node1\n",
    "            \n",
    "            if node1.isLeaf and node1.val:  return node1\n",
    "            if node2.isLeaf and node2.val:  return node2\n",
    "\n",
    "            node1.topLeft = dfs(node1.topLeft, node2.topLeft)\n",
    "            node1.topRight = dfs(node1.topRight, node2.topRight)\n",
    "            node1.bottomLeft = dfs(node1.bottomLeft, node2.bottomLeft)\n",
    "            node1.bottomRight = dfs(node1.bottomRight, node2.bottomRight)\n",
    "            if node1.topLeft and node1.topRight and node1.bottomLeft and node1.bottomRight and node1.topLeft.val + node1.topRight.val + node1.bottomLeft.val + node1.bottomRight.val + node1.topLeft.isLeaf + node1.topRight.isLeaf + node1.bottomLeft.isLeaf + node1.bottomRight.isLeaf == 8:\n",
    "                node1.topLeft = node1.topRight = node1.bottomLeft = node1.bottomRight = None\n",
    "                node1.val = 1\n",
    "                node1.isLeaf = 1\n",
    "            else:\n",
    "                node1.isLeaf &= node2.isLeaf\n",
    "            return node1\n",
    "        return dfs(quadTree1, quadTree2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf and quadTree2.isLeaf: \n",
    "            print(quadTree1.val, quadTree2.val)\n",
    "            return Node(val = quadTree1.val | quadTree2.val, isLeaf = True)\n",
    "        if quadTree1.isLeaf and quadTree1.val == 1: return Node(val = True, isLeaf = True)\n",
    "        if quadTree2.isLeaf and quadTree2.val == 1: return Node(val = True, isLeaf = True)\n",
    "        if quadTree1.isLeaf: return quadTree2\n",
    "            # tl = self.intersect(quadTree1, quadTree2.topLeft)\n",
    "            # tr = self.intersect(quadTree1, quadTree2.topRight)\n",
    "            # bl = self.intersect(quadTree1, quadTree2.bottomLeft)\n",
    "            # br = self.intersect(quadTree1, quadTree2.bottomRight)\n",
    "            # if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val == tr.val and tr.val == bl.val and bl.val == br.val: return Node(val = tl.val, isLeaf = True)\n",
    "            # return Node(val = False, isLeaf = False, topLeft = tl, topRight = tr, bottomLeft = bl, bottomRight = br)\n",
    "        elif quadTree2.isLeaf: return quadTree1\n",
    "        else:\n",
    "            tl = self.intersect(quadTree1.topLeft, quadTree2.topLeft)\n",
    "            tr = self.intersect(quadTree1.topRight, quadTree2.topRight)\n",
    "            bl = self.intersect(quadTree1.bottomLeft, quadTree2.bottomLeft)\n",
    "            br = self.intersect(quadTree1.bottomRight, quadTree2.bottomRight)\n",
    "            if tl.isLeaf and tr.isLeaf and bl.isLeaf and br.isLeaf and tl.val == tr.val and tr.val == bl.val and bl.val == br.val: return Node(val = tl.val, isLeaf = True)\n",
    "            return Node(val = False, isLeaf = False, topLeft = tl, topRight = tr, bottomLeft = bl, bottomRight = br)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        if quadTree1.isLeaf: return quadTree1 if quadTree1.val else quadTree2\n",
    "        if quadTree2.isLeaf: return quadTree2 if quadTree2.val else quadTree1\n",
    "        tl = self.intersect(quadTree1.topLeft,quadTree2.topLeft)\n",
    "        tr = self.intersect(quadTree1.topRight,quadTree2.topRight)\n",
    "        bl = self.intersect(quadTree1.bottomLeft,quadTree2.bottomLeft)\n",
    "        br = self.intersect(quadTree1.bottomRight,quadTree2.bottomRight)\n",
    "        l = [tl,tr,bl,br]\n",
    "        if all(node.isLeaf and node.val for node in l): return Node(1,True)\n",
    "        return Node(0,False,*l)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        nod = Node(quadTree1.val or quadTree2.val, False, None, None, None, None)\n",
    "        if quadTree1.isLeaf and quadTree2.isLeaf or quadTree1.isLeaf and quadTree1.val or quadTree2.isLeaf and quadTree2.val:\n",
    "            nod.isLeaf = True\n",
    "            return nod\n",
    "        elif quadTree1.isLeaf:\n",
    "            nod.topLeft = self.intersect(quadTree1, quadTree2.topLeft)\n",
    "            nod.topRight = self.intersect(quadTree1, quadTree2.topRight)\n",
    "            nod.bottomLeft = self.intersect(quadTree1, quadTree2.bottomLeft)\n",
    "            nod.bottomRight = self.intersect(quadTree1, quadTree2.bottomRight)\n",
    "            if nod.topLeft.val == nod.topRight.val == nod.bottomLeft.val == nod.bottomRight.val and nod.topLeft.isLeaf and nod.topRight.isLeaf and nod.bottomLeft.isLeaf and nod.bottomRight.isLeaf:\n",
    "                nod.isLeaf = True\n",
    "                nod.val = nod.topLeft.val\n",
    "                nod.topLeft, nod.topRight, nod.bottomLeft, nod.bottomRight = None, None, None, None\n",
    "            return nod\n",
    "        elif quadTree2.isLeaf:\n",
    "            nod.topLeft = self.intersect(quadTree2, quadTree1.topLeft)\n",
    "            nod.topRight = self.intersect(quadTree2, quadTree1.topRight)\n",
    "            nod.bottomLeft = self.intersect(quadTree2, quadTree1.bottomLeft)\n",
    "            nod.bottomRight = self.intersect(quadTree2, quadTree1.bottomRight)\n",
    "            if nod.topLeft.val == nod.topRight.val == nod.bottomLeft.val == nod.bottomRight.val and nod.topLeft.isLeaf and nod.topRight.isLeaf and nod.bottomLeft.isLeaf and nod.bottomRight.isLeaf:\n",
    "                nod.isLeaf = True\n",
    "                nod.val = nod.topLeft.val\n",
    "                nod.topLeft, nod.topRight, nod.bottomLeft, nod.bottomRight = None, None, None, None\n",
    "            return nod\n",
    "        else:\n",
    "            nod.topLeft = self.intersect(quadTree2.topLeft, quadTree1.topLeft)\n",
    "            nod.topRight = self.intersect(quadTree2.topRight, quadTree1.topRight)\n",
    "            nod.bottomLeft = self.intersect(quadTree2.bottomLeft, quadTree1.bottomLeft)\n",
    "            nod.bottomRight = self.intersect(quadTree2.bottomRight, quadTree1.bottomRight)\n",
    "            if nod.topLeft.val == nod.topRight.val == nod.bottomLeft.val == nod.bottomRight.val and nod.topLeft.isLeaf and nod.topRight.isLeaf and nod.bottomLeft.isLeaf and nod.bottomRight.isLeaf:\n",
    "                nod.isLeaf = True\n",
    "                nod.val = nod.topLeft.val\n",
    "                nod.topLeft, nod.topRight, nod.bottomLeft, nod.bottomRight = None, None, None, None\n",
    "            return nod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\"\"\"\n",
    "# Definition for a QuadTree node.\n",
    "class Node:\n",
    "    def __init__(self, val, isLeaf, topLeft, topRight, bottomLeft, bottomRight):\n",
    "        self.val = val\n",
    "        self.isLeaf = isLeaf\n",
    "        self.topLeft = topLeft\n",
    "        self.topRight = topRight\n",
    "        self.bottomLeft = bottomLeft\n",
    "        self.bottomRight = bottomRight\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def intersect(self, quadTree1: 'Node', quadTree2: 'Node') -> 'Node':\n",
    "        def DFS(node1, node2):\n",
    "            if node1.isLeaf:\n",
    "                if node1.val:\n",
    "                    return Node(1,1)\n",
    "                else:\n",
    "                    return node2\n",
    "            if node2.isLeaf:\n",
    "                return DFS(node2, node1)\n",
    "            c1 = DFS(node1.topLeft, node2.topLeft)\n",
    "            c2 = DFS(node1.topRight, node2.topRight)\n",
    "            c3 = DFS(node1.bottomLeft, node2.bottomLeft)\n",
    "            c4 = DFS(node1.bottomRight, node2.bottomRight)\n",
    "            if c1.isLeaf and c2.isLeaf and c3.isLeaf and c4.isLeaf and c1.val == c2.val == c3.val == c4.val:\n",
    "                return Node(c1.val, 1)\n",
    "            else:\n",
    "                return Node(1, 0, c1, c2, c3, c4)\n",
    "\n",
    "        return DFS(quadTree1, quadTree2)\n",
    "            \n",
    "\n",
    "        "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
